package com.shm.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 77. 组合
 * 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
 *
 * 示例:
 *
 * 输入: n = 4, k = 2
 * 输出:
 * [
 *   [2,4],
 *   [3,4],
 *   [2,3],
 *   [1,2],
 *   [1,3],
 *   [1,4],
 * ]
 * @author SHM
 */
public class Combine {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();

    /**
     * 方法一：递归实现组合型枚举
     * 思路与算法
     *
     * 从 nn 个当中选 kk 个的所有方案对应的枚举是组合型枚举。在「方法一」中我们用递归来实现组合型枚举。
     * dfs(cur,n) 参数表示当前位置是 \rm curcur，原序列总长度为 nn。原序列的每个位置在答案序列种的状态有被选中和不被选中两种，我们用 \rm temptemp 数组存放已经被选出的数字。在进入 {\rm dfs(cur,} n)dfs(cur,n) 之前 \rm [1, cur - 1][1,cur−1] 位置的状态是确定的，而 [{\rm cur}, n][cur,n] 内位置的状态是不确定的，{\rm dfs(cur,} n)dfs(cur,n) 需要确定 \rm curcur 位置的状态，然后求解子问题 {\rm dfs(cur + 1}, n)dfs(cur+1,n)。对于 \rm curcur 位置，我们需要考虑 a[{\rm cur}]a[cur] 取或者不取，如果取，我们需要把 a[{\rm cur}]a[cur] 放入一个临时的答案数组中（即上面代码中的 \rm temptemp），再执行 {\rm dfs(cur + 1}, n)dfs(cur+1,n)，执行结束后需要对 \rm temptemp 进行回溯；如果不取，则直接执行 {\rm dfs(cur + 1}, n)dfs(cur+1,n)。在整个递归调用的过程中，\rm curcur 是从小到大递增的，当 \rm curcur 增加到 n + 1n+1 的时候，记录答案并终止递归。可以看出二进制枚举的时间复杂度是 O(2 ^ n)O(2
     * n
     *  )。
     *
     * 组合枚举的代码框架可以借鉴二进制枚举。例如我们需要在 nn 个元素选 kk 个，在 \rm dfsdfs 的时候需要多传入一个参数 kk，即 {\rm dfs(cur}, n, k)dfs(cur,n,k)。在每次进入这个 \rm dfsdfs 函数时，我们都去判断当前 \rm temptemp 的长度是否为 kk，如果为 kk，就把 \rm temptemp 加入答案并直接返回，即：
     *
     * 这个时候我们可以做一个剪枝，如果当前 \rm temptemp 的大小为 ss，未确定状态的区间 [{\rm cur}, n][cur,n] 的长度为 tt，如果 s + t < ks+t<k，那么即使 tt 个都被选中，也不可能构造出一个长度为 kk 的序列，故这种情况就没有必要继续向下递归，即我们可以在每次递归开始的时候做一次这样的判断：
     *
     * 至此，其实我们已经得到了一个时间复杂度为 O({n \choose k})O((
     * k
     * n
     * ​
     *  )) 的组合枚举，由于每次记录答案的复杂度为 O(k)O(k)，故这里的时间复杂度为 O({n \choose k} \times k)O((
     * k
     * n
     * ​
     *  )×k)，但是我们还可以进一步优化代码。在上面这份代码中有三个 \rm ifif 判断，其实第三处的 \rm ifif 是可以被删除的。因为：
     *
     * 首先，{\rm cur} = n + 1cur=n+1 的时候，一定不可能出现 s > ks>k（ss 是前文中定义的 \rm temptemp 的大小），因为自始至终 ss 绝不可能大于 kk，它等于 kk 的时候就会被第二处 \rm ifif 记录答案并返回；
     * 如果 {\rm cur} = n + 1cur=n+1 的时候 s = ks=k，它也会被第二处 \rm ifif 记录答案并返回；
     * 如果 {\rm cur} = n + 1cur=n+1 的时候 s < ks<k，一定会在 {\rm cur} < n + 1cur<n+1 的某个位置的时候发现 s + t < ks+t<k，它也会被第一处 \rm ifif 剪枝。
     *
     * 复杂度分析
     *
     * 时间复杂度：O({n \choose k} \times k)O((
     * k
     * n
     * ​
     *  )×k)，分析见「思路」部分。
     * 空间复杂度：O(n + k) = O(n)O(n+k)=O(n)，即递归使用栈空间的空间代价和临时数组 \rm temptemp 的空间代价。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/combinations/solution/zu-he-by-leetcode-solution/
     * @param n
     * @param k
     * @return
     */
    public List<List<Integer>> combine(int n, int k) {
        if (n<k){
            return res;
        }
        dfs(1,n,k);
        return res;
    }

    public void dfs(int cur,int n,int k){
        // 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp
        if (temp.size()+(n-cur+1)<k){
            return;
        }
        // 记录合法的答案
        if (temp.size()==k){
            res.add(new ArrayList<>(temp));

//            你用result.add(item)的话传的是item的地址，所以如果更新item里面的内容的话result里面也会变；而result.add(new ArrayList<String>(item))相当于deep copy，更新item并不会更新result里面的东西
//            res.add(temp);
            return;
        }
        // 考虑选择当前位置
        temp.add(cur);
        dfs(cur+1,n,k);
        temp.remove(temp.size()-1);
        // 考虑不选择当前位置
        dfs(cur+1,n,k);
    }



    public List<List<Integer>> combine_2(int n, int k) {
        if(n < k || n <= 0 || k <= 0){
            return res;
        }
        dfs(n, k, 1, 1, new ArrayList<>());
        return res;
    }

    //index表示这是组合中的第几个数字
    public void dfs(int n, int k, int index, int start, List<Integer> list){
        for(int i = start; i <= n - k + index; i++){
            list.add(i);
            if(index == k){
                res.add(new ArrayList<>(list));
            }else{
                dfs(n, k, index + 1, i + 1, list);
            }
            list.remove(list.size() - 1);
        }
    }


    public void dfs(int n, int k, int start, List<Integer> list){
        for(int i = start; i <= n - k + list.size()+1; i++){
            list.add(i);
            if(list.size() == k){
                res.add(new ArrayList<>(list));
            }else{
                dfs(n, k, i + 1, list);
            }
            list.remove(list.size() - 1);
        }
    }
}
